package com.yuqian.JavaSe.leetcode.easy;

import java.util.Arrays;

/**
 * Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.
 * @author yuqian
 *
 *找出个数为n的数组中某个元素（元素个数大于n/2）
 */
public class MajorityElement {
	 public int majorityElement(int[] nums) {
		 	//排序
	        Arrays.sort(nums);
	        return nums[nums.length/2];
	    }
	 
	 //一种更好的解法(O(n)时间复杂度，O(1)空间复杂度)
	 public class Solution {
		    public int majorityElement(int[] num) {

		        int major=num[0], count = 1;
		        for(int i=1; i<num.length;i++){
		            if(count==0){
		                count++;
		                major=num[i];
		            }else if(major==num[i]){
		                count++;
		                if(count>num.length/2){
		                	break;
		                }
		            }else count--;
		            
		        }
		        return major;
		    }
		}
}
